import java.util.ArrayList;
import java.util.List;

/**
 * 17.  Letter Combinations Of A Phone Number 电话号码的字母组合
 * https://leetcode.com/problems/letter-combinations-of-a-phone-number/
 */
class LetterCombinationsOfAPhoneNumber {
    private static final String[] MAPPING = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    /**
     * 方法：使用回溯算法生成电话号码的所有字母组合
     * 
     * Args:
     *   digits: String - 输入的数字字符串，每个数字对应电话键盘上的字母
     * 
     * Returns:
     *   List<String> - 包含所有可能字母组合的列表
     * 
     * Time: O(n4^n) - 最坏情况下每个数字对应4个字母，n是数字长度
     * Space: O(n) - 递归调用栈的深度为n，不考虑输出空间
     */
    public List<String> letterCombinations(String digits) {
        int n = digits.length();
        if(n == 0){
            return List.of();
        }
        List<String> ans = new ArrayList<>();
        char[] path = new char[n];
        backtrack(0, ans, path, digits.toCharArray());
        return ans;
    }

    private void backtrack(int i, List<String> ans, char[] path, char[] digits){
        if(i == digits.length){
            ans.add(new String(path));
            return;
        }
        String letters = MAPPING[digits[i] - '0'];
        for(char c : letters.toCharArray()){
            path[i] = c;
            backtrack(i+1, ans, path, digits);
        }
    }
}